<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <title>快速排序</title>
  </head>

  <body>
    <script>
      /*
       * 快速排序（quick sort）思路：
       * 1.在数据集之中，选择一个元素作为"基准"（pivot）。
       * 2.所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。
       * 3.对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

       * 例如：以对数组[3, 2, 4, 5, 1] 进行从小到大排序为例，步骤如下：
       * 1.选择中间值“4”作为“支点”。
       * 2.第一个元素3小于4，左侧指针向后移动一位；第二个元素2小于4，左侧指针向后移动一位；第三个元素4等于4，左侧指针停在这个位置（数组的第2位）。
       * 3.倒数第一个元素1小于4，右侧指针停在这个位置（数组的第4位）。
       * 4.左侧指针的位置（2）小于右侧指针的位置（4），两个位置的值互换，数组变成[3, 2, 1, 5, 4]。
       * 5.左侧指针向后移动一位，第四个元素5大于4，左侧指针停在这个位置（数组的第3位）。
       * 6.右侧指针向前移动一位，第四个元素5大于4，右侧指针移动向前移动一位，第三个元素1小于4，右侧指针停在这个位置（数组的第3位）。
       * 7.左侧指针的位置（3）大于右侧指针的位置（2），本次排序结束。
       * 8.对 [3, 2, 1]和[5, 4]两部分各自不断重复上述步骤，直到排序完成。
       */
      function quickSort(arr) {
        if (arr.length == 0) {
          return arr;
        }
        var pirotIndex = Math.floor(arr.length / 2);
        var pirot = arr.splice(pirotIndex, 1)[0];
        var left = [],
          right = [];
        for (var i = 0; i < arr.length; i++) {
          if (arr[i] > pirot) {
            right.push(arr[i]);
          } else {
            left.push(arr[i]);
          }
        }
        return quickSort(left).concat(pirot, quickSort(right));
      }
      console.log(quickSort([3, 2, 4, 5, 1]));
    </script>
  </body>
</html>
